Reorder list

Time: O(N); Space: O(1); medium

Given a singly linked list L: L0 → L1 → … → Ln-1 → Ln

reorder it to: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

Example 1:

Input: head = {ListNode} 1->2->3->4->None

Output: {ListNode} 1->4->2->3->None

Example 2:

Input: head = {ListNode} 1->2->3->4->5->None

Output: {ListNode} 1->5->2->4->3->None

Challenge:

  • Can you do this in-place without altering the nodes’ values?

[1]:

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

    def __repr__(self):
        if self:
            return "{} -> {}".format(self.val, repr(self.next))

[2]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: Do not return anything, modify nums in-place instead.
        """
        if head == None or head.next == None:
            return head

        fast, slow, prev = head, head, None
        while fast != None and fast.next != None:
            fast, slow, prev = fast.next.next, slow.next, slow
        current, prev.next, prev = slow, None, None

        while current != None:
            current.next, prev, current = prev, current, current.next

        l1, l2 = head, prev
        dummy = ListNode(0)
        current = dummy

        while l1 != None and l2 != None:
            current.next, current, l1 = l1, l1, l1.next
            current.next, current, l2 = l2, l2, l2.next

        return dummy.next

[3]:

s = Solution1()

head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
s.reorderList(head)
assert head.val == 1
assert head.next.val == 4
assert head.next.next.val == 2
assert head.next.next.next.val == 3

head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
s.reorderList(head)
assert head.val == 1
assert head.next.val == 5
assert head.next.next.val == 2
assert head.next.next.next.val == 4
assert head.next.next.next.next.val == 3